package com.hjx.other;

/**
 * @author houjinxin
 * @version 创建时间：2019/10/30.
 */
public class BinarySearch {

    public static int binarySearch(int[] a, int target){

        int low = 0;
        int high = a.length - 1;
        return search(a, low, high, target);

    }

    /**
     * 递归式二分查找 O(logn), 分治法不断减小数据的规模
     * 基准条件，找不到 或者 高低位之间元素为1时 是否等于目标值
     * 递归条件，比较大小后每次舍弃一半的数据
     *
     * @param a
     * @param low
     * @param high
     * @param target
     * @return
     */
    public static int search(int[] a, int low, int high, int target){
        System.out.println(String.format("执行search %s %s ", low, high));
        if (low > high){
            return -1;
        }
        int mid = (low + high) / 2;
        if (a[mid] > target){
            high = mid - 1;
            return search(a, low, high, target);
        } else if(a[mid] < target){
            low = mid + 1;
            return search(a, low, high, target);
        } else {
            return mid;
        }
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9};

//        System.out.println(binarySearch(a, 1));
//        System.out.println(binarySearch(a, 2));
//        System.out.println(binarySearch(a, 3));
//        System.out.println(binarySearch(a, 4));
//        System.out.println(binarySearch(a, 5));
//        System.out.println(binarySearch(a, 6));
//        System.out.println(binarySearch(a, 7));
//        System.out.println(binarySearch(a, 8));
//        System.out.println(binarySearch(a, 9));

        System.out.println(binarySearch(a, 0));

    }
}
